Markov random fields are a popular model for high-dimensional probability distributions. Over the years, many mathematical, statistical and algorithmic problems on them have been studied. Until recently, the only known algorithms for provably learning them relied on exhaustive search, correlation decay or various incoherence assumptions. Bresler gave an algorithm for learning general Ising models on bounded degree graphs. His approach was based on a structural result about mutual information in Ising models. Here we take a more conceptual approach to proving lower bounds on the mutual information.

This paper is concerned with learning Markov random fields (MRF). It is a theoretical paper, which is ultimately focused with proving a particular statement: given a variable X in an MRF, and given some of its Markov blanket variables B, there exists another variable Y that is conditionally dependent on X given the subset of B. In general this statement is not true; so the goal here is to identify some conditions where this is true. Most of this paper is centered around this, from which the ability to learn an MRF follows. The paper is mostly technical; my main complaint is that I do not think it is very intuitive. It appears that central to the results is the assumption on non-degeneracy, which I believe should be explained in higher level terms.

Markov random fields are a popular model for high-dimensional probability distributions. Over the years, many mathematical, statistical and algorithmic problems on them have been studied. Until recently, the only known algorithms for provably learning them relied on exhaustive search, correlation decay or various incoherence assumptions. Bresler gave an algorithm for learning general Ising models on bounded degree graphs. His approach was based on a structural result about mutual information in Ising models.